题意：

$N\le 5\times 10^5，给定二维平面上N个点，定义距离为欧氏距离的平方$
$挨个加入每个点，对于i>1的所有点，求[1,i]的最近点对距离，输出这些距离和$

分析：

$考虑离线，倒着做，求一次最近点对，假设得到的点为(p, q)，p < q$
$那么显然[q,n]的答案都是dis(p,q)$
$去掉[q,n]这些点，做[1,q-1]的部分，成为子问题$
$由于是随机数据，每次问题规模下降1/3，所以总体复杂度大概是O(nlog^2n)$

$其实还可以直接暴力，挨个添加点到set，设当前答案为d$
$对于每个点，设坐标为(x,y)，暴力查询横坐标在[x-d, x+d]范围的点$
$由于随机数据，答案下降的很快，所以跑的飞快$
$时间复杂度大概在O(nlogn)$

第一种解法代码：

//
//  Created by TaoSama on 2016-03-18
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 5e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;
typedef pair<int, int> P;
typedef long long LL;
P a[N]; int id[N];

pair<LL, P> dfs(int l, int r) {
    if(l == r) return {~0ull >> 2, { -1, -1}};
    int m = l + r >> 1;
    LL x = a[id[m]].first;

    auto ret = min(dfs(l, m), dfs(m + 1, r));
    inplace_merge(id + l, id + m + 1, id + r + 1, [](int x, int y) {
        return a[x].second < a[y].second;
    });

    vector<int> v;
    for(int i = l; i <= r; ++i) {
        int p = id[i];
        if((a[p].first - x) * (a[p].first - x) >= ret.first) continue;
        for(int j = 0; j < v.size(); ++j) {
            int q = v[v.size() - 1 - j];
            LL dy = a[p].second - a[q].second;
            if(dy * dy >= ret.first) break;
            LL dx = a[p].first - a[q].first;
            LL d = dx * dx + dy * dy;
            if(d < ret.first) ret = {d, {p, q}};
        }
        v.push_back(p);
    }
    return ret;
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int a1, b1, c1, a2, b2, c2;
        scanf("%d%d%d", &a1, &b1, &c1);
        scanf("%d%d%d", &a2, &b2, &c2);
        for(int i = 1; i <= n; ++i) {
            a[i].first = (1LL * a1 * a[i - 1].first + b1) % c1;
            a[i].second = (1LL * a2 * a[i - 1].second + b2) % c2;
        }

        LL ans = 0;
        for(int r = n; r > 1;) {
            for(int i = 1; i <= r; ++i) id[i] = i;
            sort(id + 1, id + 1 + r, [](int x, int y) {
                return a[x] < a[y];
            });
            auto cp = dfs(1, r);
            int nxt = max(cp.second.first, cp.second.second);

            ans += cp.first * (r - nxt + 1);
            r = nxt - 1;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}